Corelab Seminar
2015-2016
Andreas Goebel
Asymptotically tight bounds for inefficiency in risk-averse selfish routing
Abstract.
We consider a nonatomic selfish routing model with independent stochastic travel times, represented by mean and variance latency functions for each edge that depend on their flows. In an effort to decouple the effect of risk-averse player preferences from selfish behavior on the degradation of system performance, Nikolova and Stier- Moses [16] defined the concept of the price of risk aversion as the worst-case ratio of the cost of an equilibrium with risk-averse players (who seek risk-minimizing paths, for an appropriate definition of risk) and that of an equilibrium with risk-neutral users (who minimize the mean travel time of a path). For risk-averse users who seek to minimize the mean plus variance of travel time on a path, they proved an upper bound on the price of risk aversion, which is independent of the mean and variance latency functions, and grows linearly with the size of the graph and players’ risk-aversion.
In this follow-up paper, we provide a matching lower bound for graphs with number of vertices equal to powers of two, via the construction of a graph family inductively generated from the Braess graph. In contrast to these topological bounds that depend on the topology of the network, we also provide conceptually different bounds, which we call functional. These bounds depend on the class of mean latency functions that are allowed and provide characterizations that are independent of the network topology. The functional upper bound was first derived by Meir and Parkes [10] in a different context with different techniques; we offer a simpler, direct proof that is inspired by a classic proof technique using variational inequalities [7]. We also supplement the upper bound with a new asymptotically-tight lower bound, derived from the same graph construction as the topological lower bound. Thus, we offer a conceptually new perspective and understanding of both this and classic congestion game settings in terms of the functional versus topological view of efficiency loss.
Our third contribution is a tight bound on the price of risk aversion for a family of graphs that generalize series-parallel graphs and the Braess graph. That bound applies to both users minimizing the mean plus variance (mean-var) of a path, as well as to users minimizing the mean plus standard deviation (mean-stdev) of a path—a much more complex model of risk-aversion due to the cost of a path being non-additive over edge costs. This is a refinement of previous results in [16] that characterized the price of risk-aversion for series-parallel graphs and for the Braess graph. The main question left open is to upper bound the price of risk-aversion in the mean-stdev model for general graphs; our lower bounds apply to both the mean-var and the mean-stdev models.